package com.sunny.example.primenumber;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 素数伴侣
 * 两个数相加的和为素数的技巧：一个奇数与一个偶数
 */
public class PrimeNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            int[] inputs = new int[num];
            for (int i = 0; i < num; i++) {
                inputs[i] = scanner.nextInt();
            }

            //计算两两值相加是否为素数
            int count = 0;//素数伴侣最多的方案
            List<Integer> okList = new ArrayList<>();//对于相加之和为素数的数，只能参与一次。
            //1、先计算和，两个数相加的和为素数的技巧：一个奇数与一个偶数
            List<Integer> oddList = new ArrayList<>();//奇数列表
            List<Integer> evenList = new ArrayList<>();//偶数列表
            for (int j = 0; j < inputs.length; j++) {
                if (inputs[j] % 2 == 0) {
                    //偶数
                    evenList.add(inputs[j]);
                } else  {//奇数
                    oddList.add(inputs[j]);
                }
            }
            int[] evenMatches = new int[evenList.size()];//偶数的伴侣数
            for (int j = 0; j < oddList.size(); j++) { //循环奇数
                //每个奇数，与偶数相加
                int a1 = oddList.get(j);
                //用于标记对应的偶数是否查找过
                boolean[] matched = new boolean[evenList.size()];
                if (findMatch(a1, evenMatches, evenList, matched)) {
                    count++;
                }
            }
            System.out.println(count);

        }

    }

    private static boolean findMatch(int value, int[] evenMatches, List<Integer> evenList, boolean[] matched/*List<Integer> okList*/) {
        for (int k = 0; k < evenList.size(); k++) {
            int a2 = evenList.get(k);
            int sum = value + a2;
            boolean isPrime = PrimeUtils.findPrimeNum(sum);
            if (isPrime && matched[k] == false/*!okList.contains(value)*/) {
                //只要这个偶数还没有使用过，则添加进okList，
                //如果这个偶数还没有伴侣，或者已经有伴侣，再重新找另外的伴侣
//                        count++;
//                okList.add(value);
                matched[k] = true;
                if (evenMatches[k] == 0 || findMatch(evenMatches[k], evenMatches, evenList, matched)) {
                    evenMatches[k] = value;
                    return true;
                }
            }
        }
        return false;
    }


}
